翻訳と辞書
Words near each other
・ Disjointed Parallels
・ Disjunct
・ Disjunct (linguistics)
・ Disjunct distribution
・ Disjunct matrix
・ Disjunction and existence properties
・ Disjunction elimination
・ Disjunction introduction
・ Disjunction property of Wallman
・ Disjunctive
・ Disjunctive cognition
・ Disjunctive graph
・ Disjunctive normal form
・ Disjunctive population
・ Disjunctive pronoun
Disjunctive sequence
・ Disjunctive sum
・ Disjunctive syllogism
・ Disjunctivism
・ Disk (mathematics)
・ Disk 413
・ Disk aggregation
・ Disk algebra
・ Disk array
・ Disk array controller
・ Disk buffer
・ Disk cache
・ Disk cartridge
・ Disk Cleanup
・ Disk cloning


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Disjunctive sequence : ウィキペディア英語版
Disjunctive sequence
A disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. For instance, the binary Champernowne sequence
:0\ 1\ 00\ 01\ 10\ 11\ 000\ 001 \ldots
formed by concatenating all binary strings in shortlex order, clearly contains all the binary strings and so is disjunctive. (The spaces above are not significant and are present solely to make clear the boundaries between strings). The complexity function of a disjunctive sequence ''S'' over an alphabet of size ''k'' is ''p''''S''(''n'') = ''k''''n''.〔Bugeaud (2012) p.91〕
Any normal sequence (a sequence in which each string of equal length appears with equal frequency) is disjunctive, but the converse is not true. For example, letting 0''n'' denote the string of length ''n'' consisting of all 0s, consider the sequence
:0\ 0^1\ 1\ 0^2\ 00\ 0^4\ 01\ 0^8\ 10\ 0^\ 11\ 0^\ 000\ 0^\ldots
obtained by splicing exponentially long strings of 0s into the shortlex ordering of all binary strings. Most of this sequence consists of long runs of 0s, and so it is not normal, but it is still disjunctive.
==Examples==

The following result〔
〕〔
〕 can be used to generate a variety of disjunctive sequences:
:If ''a''1, ''a''2, ''a''3, ..., is a strictly increasing infinite sequence of positive integers such that lim ''n'' → ∞ (''a''''n''+1 / ''a''''n'') = 1,
:then for any positive integer ''m'' and any integer base ''b'' ≥ 2, there is an ''a''''n'' whose expression in base ''b'' starts with the expression of ''m'' in base ''b''.
:(Consequently, the infinite sequence obtained by concatenating the base-''b'' expressions for ''a''1, ''a''2, ''a''3, ..., is disjunctive over the alphabet .)
Two simple cases illustrate this result:
* ''a''''n'' = ''n''''k'', where ''k'' is a fixed positive integer. (In this case, lim ''n'' → ∞ (''a''''n''+1 / ''a''''n'') = lim ''n'' → ∞ ( (''n''+1)''k'' / ''n''''k'' ) = lim ''n'' → ∞ (1 + 1/''n'')''k'' = 1.)
: E.g., using base-ten expressions, the sequences
:: 123456789101112... (''k'' = 1, positive natural numbers),
:: 1491625364964... (''k'' = 2, squares),
:: 182764125216343... (''k'' = 3, cubes),
:: etc.,
:are disjunctive on .
* ''a''''n'' = ''p''''n'', where ''p''''n'' is the ''n''th prime number. (In this case, lim ''n'' → ∞ (''a''''n''+1 / ''a''''n'') = 1 is a consequence of ''p''''n'' ~ ''n'' ln ''n''.)
: E.g., the sequences
:: 23571113171923... (using base ten),
:: 10111011111011110110001 ... (using base two),
:: etc.,
are disjunctive on the respective digit sets.
Another result〔http://matwbn.icm.edu.pl/ksiazki/aa/aa81/aa8143.pdf〕 that provides a variety of disjunctive sequences is as follows:
:If ''a''''n'' = floor(''f''(''n'')), where ''f'' is any non-constant polynomial with real coefficients such that ''f''(''x'') > 0 for all ''x'' > 0,
:then the concatenation ''a''''1''''a''''2''''a''''3''... (with the ''a''''n'' expressed in base ''b'') is a normal sequence in base ''b'', and is therefore disjunctive on .
E.g., using base-ten expressions, the sequences
:: 818429218031851879211521610... (with ''f''(''x'') = 2''x''3 - 5''x''2 + 11''x'' )
:: 591215182124273034... (with ''f''(''x'') = π''x'' + e)
are disjunctive on .

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Disjunctive sequence」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.